package alo.p6.work;


import java.util.LinkedList;
import java.util.Queue;

/**
 * @ClassName FillNextSiblings
 * @Description 填充下一个兄弟指针，root无兄弟，2的为3，3无，4为5，5为6，6为7，7无
 * @Author Fanxc
 * @DATE 2021/2/1 11:58
 * @Version 1.0
 */
public class FillNextSiblings {
    //层序遍历，每一层添加一个null，每一个结点的下一个兄弟指针为队列的下一个
    //1 null 2 3 null 4 5 6 7 null
    void fillNextSiblings(BinaryTreeNode root) {
        Queue<BinaryTreeNode> queue = new LinkedList<>();
        BinaryTreeNode temp = null;
        if(root==null){
            return;
        }
        queue.offer(root);
        queue.offer(null);
        while (!queue.isEmpty()){
            temp= queue.poll();
            //遇到null
            if (temp==null){
                //当一层（不是最后一层）遍历完成，加一个null
                if (!queue.isEmpty()){
                    queue.offer(null);
                }
            }else {
                temp.setNextSibling(queue.peek());
                if (temp.getLeft()!=null){
                    queue.offer(temp.getLeft());
                }
                if (temp.getRight()!=null){
                    queue.offer(temp.getRight());
                }
            }
        }
    }

    //使用递归
    void fillNextSiblings2(BinaryTreeNode root) {
        if (root==null){
            return;
        }
        //如果左孩子存在，把右孩子设置为左孩子的下一个兄弟指针（无论为不为null）
        if (root.getLeft()!=null){
            root.getLeft().setNextSibling(root.getRight());
        }
        //如果有孩子存在
        if (root.getRight()!=null){
            //如果root的下一个兄弟存在，则把兄弟的左孩子设置为root的右孩子的下一个兄弟
            // （即2的兄弟3存在，则设置2的右孩子5的下一个兄弟为3的左孩子6）
            //否则设置为null
            if (root.getNextSibling()!=null){
                root.getRight().setNextSibling(root.getNextSibling().getLeft());
            }else {
                root.getRight().setNextSibling(null);
            }
        }
        fillNextSiblings2(root.getLeft());
        fillNextSiblings2(root.getRight());
    }
    //三指针的二叉树的定义
    static class BinaryTreeNode{
        //数据和左右子树的定义
        private int data;
        private BinaryTreeNode left;
        private BinaryTreeNode right;
        private BinaryTreeNode nextSibling;

        //数据的get和set方法
        public int getData() {
            return data;
        }
        public void setData(int data) {
            this.data = data;
        }
        //左子树的get和set方法
        public BinaryTreeNode getLeft() {
            return left;
        }
        public void setLeft(BinaryTreeNode left) {
            this.left = left;
        }

        //右子树的get和set方法
        public BinaryTreeNode getRight() {
            return right;
        }
        public void setRight(BinaryTreeNode right) {
            this.right = right;
        }

        public BinaryTreeNode getNextSibling() {
            return nextSibling;
        }

        public void setNextSibling(BinaryTreeNode nextSibling) {
            this.nextSibling = nextSibling;
        }
    }
}
